package pr;

public class Shuangxiang<E> {
    private Node head;
    private int size;

    private class Node {
        Node next;
        Node prev;
        E data;

        Node(E e) {
            data = e;
        }
    }

    public boolean add(E e) {
        if (head == null) {
            head = new Node(e);
            head.next = head;
            head.prev = head;
        } else {
            Node node = new Node(e);
            Node last = head.prev;
            node.next = head;
            node.prev = last;
            last.next = node;
            head.prev = node;
        }
        size++;
        return true;
    }

    public String toString() {
        if (head == null) {
            return "[]";
        }
        StringBuilder bu = new StringBuilder("[");
        bu.append(head.data);
        Node node = head.next;
        while (node != head) {
            bu.append(",");
            bu.append(node.data);
            node = node.next;
        }
        bu.append("]");
        return bu.toString();

    }

    public E get(int index) {
        return find(index).data;
    }

    private Node find(int index) {
        Node node;
        if (index < size >> 1) {
            node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }

        } else {
            node = head.prev;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }

        }
        return node;
    }

    public boolean add(int index, E e) {
        Node node=new Node(e);
        Node next=find(index);
        Node prev=next.prev;
        node.prev=prev;
        node.next=next;
        next.prev=node;
        prev.next=node;
        size++;
        return true;
       
    }

    public E remove(int index) {
        if (size==1) {
            E e=head.data;
            head=null;
            size--;
            return e;
        }
        Node node=find(index);
        Node next=node.next;
        Node prev=node.prev;
        next.prev=prev;
        prev.next=next;
        node.prev=null;
        node.next=null;
        if (index==0) {
            head=next;
        }
        size--;
        return node.data;
    }

    public static void main(String[] args) {
        Shuangxiang<String> sh = new Shuangxiang<>();
        sh.add("s");
        sh.add("b");
        sh.add("f");
        sh.add("w");
        System.out.println(sh.toString());
        System.out.println(sh.get(3));
        sh.add(3,"l");
        System.out.println(sh.toString());
        sh.remove(3);
        System.out.println(sh.toString());
    }

}
